public class TextDemo {
    public static void heapSort(int[] array){
        buildMaxHeap(array);
    }
    public static void buildMaxHeap(int[] array){
        for(int i = (array.length>>1)-1;i>=0;i--){
            maxHeapify(array,i,array.length);
        }
    }
    public static void maxHeapify(int[] array,int i,int heapSize){
        int largest = i;
        int child = (2*i)+1;
        if(child+1<heapSize&&array[child+1]>array[child]){
            child++;
        }
        if(array[largest]<array[child]){
            swap(array,largest,child);
            maxHeapify(array,largest,heapSize);
        }
    }
    public static void swap(int[] array,int x,int y){
        int tem = array[x];
        array[x] = array[y];
        array[y] = tem;
    }
}
